package com.leetcode.algorithm.y18.m06;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * leetcode-cn.com
 * (done)485. 最大连续1的个数
 * (done)532. 数组中的K-diff数对
 * (done)561. 数组拆分 I
 * (done)566. 重塑矩阵
 * (done)581. 最短无序连续子数组
 * (done)605. 种花问题
 * @author: jie.deng
 * @time: 2018年6月7日 上午9:48:58
 */
public class MySolution0607 {
	/**
	 * 485. 最大连续1的个数
     * 给定一个二进制数组， 计算其中最大连续1的个数。
     * 
     * 示例 1:
     * 
     * 输入: [1,1,0,1,1,1]
     * 输出: 3
     * 解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.
     * 注意：
     * 
     * 输入的数组只包含 0 和1。
     * 输入数组的长度是正整数，且不超过 10,000。
	 * @param nums
	 * @return
	 */
	public int findMaxConsecutiveOnes(int[] nums) {
		int maxCount = 0;
		int fromIdx = -1;
		int i = 0;
		int len = nums.length;
		while (i < len) {
			if (nums[i] == 0) {
				if (fromIdx != -1) {
					maxCount = Math.max(maxCount, i - fromIdx);
					fromIdx = -1;
				}
			} else {
				if (fromIdx == -1) {
					fromIdx = i;
				}
			}
			i++;
		}
		if (fromIdx != -1) {
			maxCount = Math.max(maxCount, i - fromIdx);
			fromIdx = -1;
		}
		return maxCount;
	}
    
    /**
     * 532. 数组中的K-diff数对
     * 给定一个整数数组和一个整数 k, 你需要在数组里找到不同的 k-diff 数对。这里将 k-diff 数对定义为一个整数对 (i, j), 其中 i 和 j 都是数组中的数字，且两数之差的绝对值是 k.
     * 
     * 示例 1:
     * 
     * 输入: [3, 1, 4, 1, 5], k = 2
     * 输出: 2
     * 解释: 数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
     * 尽管数组中有两个1，但我们只应返回不同的数对的数量。
     * 示例 2:
     * 
     * 输入:[1, 2, 3, 4, 5], k = 1
     * 输出: 4
     * 解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
     * 示例 3:
     * 
     * 输入: [1, 3, 1, 5, 4], k = 0
     * 输出: 1
     * 解释: 数组中只有一个 0-diff 数对，(1, 1)。
     * 注意:
     * 
     * 数对 (i, j) 和数对 (j, i) 被算作同一数对。
     * 数组的长度不超过10,000。
     * 所有输入的整数的范围在 [-1e7, 1e7]。
     * @param nums
     * @param k
     * @return
     */
	public int findPairs(int[] nums, int k) {
		int count = 0;
		if (k < 0) {
			return 0;
		}
		if (k == 0) {
			Map<Integer, Integer> map = new HashMap<Integer, Integer>();
			for (int i = 0; i < nums.length; i++) {
				Integer cnt = map.get(nums[i]);
				if (cnt == null) {
					map.put(nums[i], 1);
				} else {
					map.put(nums[i], cnt + 1);
				}
			}
			for (Entry<Integer, Integer> entry : map.entrySet()) {
				if (entry.getValue() != 1) {
					count++;
				}
			}
		} else {
			Set<Integer> set = new HashSet<Integer>();
			for (int i = 0; i < nums.length; i++) {
				set.add(nums[i]);
			}
			for (Integer i : set) {
				if (set.contains(i + k)) {
					count++;
				}
			}
		}
		return count;
	}
    
    /**
     * 561. 数组拆分 I
     * 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。
     * 
     * 示例 1:
     * 
     * 输入: [1,4,3,2]
     * 
     * 输出: 4
     * 解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
     * 提示:
     * 
     * n 是正整数,范围在 [1, 10000].
     * 数组中的元素范围在 [-10000, 10000].
     * @param nums
     * @return
     */
	public int arrayPairSum(int[] nums) {
		Arrays.sort(nums);
		int sum = 0;
		for (int i = 0; i < nums.length; i += 2) {
			sum += nums[i];
		}
		return sum;
	}
    
    /**
     * 566. 重塑矩阵
     * 在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
     * 
     * 给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
     * 
     * 重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
     * 
     * 如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
     * 
     * 示例 1:
     * 
     * 输入: 
     * nums = 
     * [[1,2],
     *  [3,4]]
     * r = 1, c = 4
     * 输出: 
     * [[1,2,3,4]]
     * 解释:
     * 行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
     * 示例 2:
     * 
     * 输入: 
     * nums = 
     * [[1,2],
     *  [3,4]]
     * r = 2, c = 4
     * 输出: 
     * [[1,2],
     *  [3,4]]
     * 解释:
     * 没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
     * 注意：
     * 
     * 给定矩阵的宽和高范围在 [1, 100]。
     * 给定的 r 和 c 都是正数。
     * @param nums
     * @param r
     * @param c
     * @return
     */
	public int[][] matrixReshape(int[][] nums, int r, int c) {
		int row = nums.length;
		if (row == 0) {
			return nums;
		}
		int col = nums[0].length;
		if (row * col != r * c) {
			return nums;
		}
		if (r == row && c == col) {
			return nums;
		}
		int[][] ret = new int[r][c];
		int seq = 0;
		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++, seq++) {
				ret[i][j] = nums[seq / col][seq % col];
			}
		}
		return ret;
	}
    
    /**
     * 581. 最短无序连续子数组
     * 给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
     * 
     * 你找到的子数组应是最短的，请输出它的长度。
     * 
     * 示例 1:
     * 
     * 输入: [2, 6, 4, 8, 10, 9, 15]
     * 输出: 5
     * 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
     * 说明 :
     * 
     * 输入的数组长度范围在 [1, 10,000]。
     * 输入的数组可能包含重复元素 ，所以升序的意思是<=。
     * @param nums
     * @return
     */
	public int findUnsortedSubarray(int[] nums) {
		int len = nums.length;
		if (len < 2) {
			return 0;
		}
		int i = 0; // 找出[0,i]为升序子数组
		for (; i < len - 1; i++) {
			if (nums[i + 1] < nums[i]) {
				break;
			}
		}
		if (i == len - 1) {
			return 0;
		}

		int j = len - 1; // 找出[j,len-1]为升序子数组
		for (; j >= 1; j--) {
			if (nums[j - 1] > nums[j]) {
				break;
			}
		}

		// 找出[i,j]子数组中的最大值和最小值
		int min = nums[i];
		int max = nums[j]; // 注意此处min未必小于max
		for (int k = i; k <= j; k++) {
			if (nums[k] < min) {
				min = nums[k];
			} else if (nums[k] > max) {
				max = nums[k];
			}
		}

		// 修正min的索引
		int minIdx = i;
		for (; minIdx >= 0; minIdx--) {
			if (nums[minIdx] <= min) {
				break;
			}
		}
		// 修正max的索引
		int maxIdx = j;
		for (; maxIdx < len; maxIdx++) {
			if (nums[maxIdx] >= max) {
				break;
			}
		}
		return len - (minIdx + 1) - (len - maxIdx);
	}
    
    /**
     * 605. 种花问题
     * 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
     * 
     * 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
     * 
     * 示例 1:
     * 
     * 输入: flowerbed = [1,0,0,0,1], n = 1
     * 输出: True
     * 示例 2:
     * 
     * 输入: flowerbed = [1,0,0,0,1], n = 2
     * 输出: False
     * 注意:
     * 
     * 数组内已种好的花不会违反种植规则。
     * 输入的数组长度范围为 [1, 20000]。
     * n 是非负整数，且不会超过输入数组的大小。
     * @param flowerbed
     * @param n
     * @return
     */
	public boolean canPlaceFlowers(int[] flowerbed, int n) {
		int len = flowerbed.length;
		if (n == 0) {
			return true;
		}
		if (len == 1) {
			return flowerbed[0] == 0 && n == 1;
		}
		// len>=2的情况
		if (len < ((n << 1) - 1)) {
			return false;
		}
		int cnt = 0;
		int i = 0;
		if (flowerbed[i] == 0 && flowerbed[i + 1] == 0) {
			flowerbed[0] = 1;
			cnt++;
			i += 2;
		} else {
			i = 1;
		}
		if (flowerbed[len - 1] == 0 && flowerbed[len - 2] == 0) {
			cnt++;
			flowerbed[len - 1] = 1;
		}
		while (i < len - 1 && cnt < n) {
			if (flowerbed[i] == 1) {
				i += 2;
			} else if ((flowerbed[i - 1] | flowerbed[i + 1]) == 0) {
				// flowerbed[i] == 0 && flowerbed[i - 1] == 0 && flowerbed[i - 1] == 0
				flowerbed[i] = 1;
				cnt++;
				i += 2;
			} else {
				// flowerbed[i] == 0 && (flowerbed[i - 1] == 1 || flowerbed[i - 1] == 1)
				i++;
			}
		}
		return cnt >= n;
	}
}
